package leetcode.jianzhioffer;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-02 10:34
 **/
public class JianZhiOffer13 {

    int m;
    int n;
    int k;
    //visted[i][j]表示当前格是否遍历过,遍历过为true,否则为false
    boolean[][] visted;
    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        this.visted = new boolean[m][n];
        return dfs(0,0,0,0);
    }

    /**
     * 深度遍历
     * @param i 当前遍历的横坐标
     * @param j 当前遍历的纵坐标
     * @param sumi 横坐标数位和
     * @param sumj 纵坐标数位和
     * @return 可以到达的格数
     */
    private int dfs(int i, int j, int sumi, int sumj) {
        //如果下标越界或者i和j的数位和>k或者当前格已遍历过，返回0
        if (i >=m || j >= n || k < sumi + sumj || visted[i][j]) {
            return 0;
        }
        //表示当前格已经被遍历过
        visted[i][j] = true;
        //递归遍历右边一格和下边一格并加上1
        return 1 + dfs(i + 1, j, get(i + 1), get(j)) + dfs(i, j + 1, get(i), get(j + 1));
    }

    //获取x的数位和
    private int get(int x) {
        int sum = 0;
        while (x!=0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
}
